Problem statement: zenit17ske

Exotické vianočné osvetlenie

Počet bodov: 25, časový limit: 500ms

Už je október – najvyšší čas vyvesiť vianočné osvetlenie, pomyslel si Dávid. Vianoce sú predsa za rohom. Konečne mu dnes doručili vianočné svetielka, ktoré si včera objednal. Bolo ich \(n\) a na jedinej šnúre boli poukladané jedno za druhým.

Ku svetielkam Dávid dostal aj ovládač so štyrmi gombíkmi, pomocou ktorých si mohol nastaviť vianočné osvetlenie podľa jeho vkusu. Ak si žiarovky na šnúre očíslujeme od \(1\) po \(n\) zľava doprava, gombíky spôsobia nasledovné: prvý prepne¹ všetky žiarovky, druhý prepne žiarovky na párnych pozíciách, tretí prepne žiarovky na nepárnych pozíciách a štvrtý prepne žiarovky na všetkých pozíciách deliteľných siedmimi.

Dávid si spravil svoju víziu: napísal si zoznam \(s\) žiaroviek, ktoré musia svietiť a zoznam \(z\) žiaroviek ktoré musia byť zhasnuté. Taktiež sa chce trochu pohrať s gombíkmi², musí preto stlačiť presne \(g\) gombíkov (niektoré môže aj viackrát).

Dávida teraz zaujíma, aké rôzne vianočné osvetlenie dokáže za týchto podmienok dosiahnuť.

Vstup a výstup

V prvom riadku je číslo \(1 \leq n \leq 10^3\) – počet žiaroviek na Dávidovom vianočnom osvetlení. Na začiatku všetky žiarovky svietia.

V druhom riadku je číslo \(0 \leq s \leq n\) – počet žiaroviek, ktoré musia svietiť. V treťom riadku je \(s\) rôznych čísel z rozsahu \(1\) až \(n\): čísla týchto žiaroviek.

V štvrtom riadku je celé číslo \(0 \leq z \leq n\) – počet žiaroviek, ktoré musia byť zhasnuté. V piatom riadku je \(z\) rôznych čísel z rozsahu \(1\) až \(n\): čísla týchto žiaroviek.

V šiestom riadku je celé číslo \(0 \leq g \leq 10^6\) – počet stlačení gombíkov, ktoré sa Dávid rozhodol vykonať.

Sú tri skupinky sád vstupov. V prvej \(n \leq 15\) a \(g \leq 8\). V druhej \(g \leq 15\).

Na výstup vypíšte všetky rôzne reťazce dlhé \(n\) znakov, každý na jeden riadok, ktoré spĺňajú nasledovné:

1. Každý znak v reťazci je 0 alebo 1. 0 značí zhasnutú žiarovku, 1 svietiaciu. Prvý znak reprezentuje prvú žiarovku, druhý druhú, … , \(n\)-tý poslednú žiarovku.
2. Na stlačenie práve \(g\) gombíkov vieme dostať takto rozsvietené žiarovky
3. Každá žiarovka v prvom Dávidovom zozname svieti a každá žiarovka v druhom Dávidovom zozname je zhasnutá.

Reťazce môžete vypísať v ľubovoľnom poradí.

 Príklad

Input:

10
0

1
7
2

Output:

0000000000
0101010101
1010100010

Jediná Dávidova požiadavka je, aby siedma lampa nesvietila. Musí stlačiť dva gombíky. Prvá možnosť je stlačiť druhý a tretí gombík. Druhá je najprv stlačiť prvý a potom druhý. Tretí reťazec dostane stlačením štvrtého a potom tretieho.

Input:

10
10
1 2 3 4 5 10 9 8 7 6
0

4

Output:

1111111111

Napríklad stlačíme prvý gombík štyrikrát.